package net.tp.algo.graph;

import java.util.*;
import java.util.function.Function;

/**
 *
 */
public class Traversal {

    public static List<Integer> bfs(Graph graph, int source) {
        List<Integer> numbers = new ArrayList<>();
        int N = graph.order();

        Queue<Integer> queue = new LinkedList<>();
        boolean[] marked = new boolean[N];

        queue.add(source);
        marked[source] = true;

        while (!queue.isEmpty()) {
            int u = queue.remove();
            numbers.add(u);

            for (int w : graph.adjacents(u)) {
                if (!marked[w]) {
                    marked[w] = true;
                    queue.add(w);
                }
            }
        }

        return numbers;
    }

    public static List<Integer> dfs(Graph graph, int source) {
        List<Integer> numbers = new ArrayList<>();
        int N = graph.order();

        Stack<Integer> stack = new Stack<>();
        boolean[] marked = new boolean[N];

        stack.add(source);
        marked[source] = true;

        while (!stack.isEmpty()) {
            int u = stack.pop();
            numbers.add(u);

            for (int w : graph.adjacents(u)) {
                if (!marked[w]) {
                    marked[w] = true;
                    stack.add(w);
                }
            }
        }

        return numbers;
    }


    public static <N> List<N> bsf(N root, Function<N, Iterable<N>> childrenGetter, Set<N> marked) {
        if (marked.contains(root)) return Collections.emptyList();

        List<N> result = new ArrayList<>();
        marked.add(root);
        Queue<N> queue = new LinkedList<>();
        queue.add(root);
        result.add(root);

        while (!queue.isEmpty()) {
            N n = queue.remove();

            Iterable<N> children = childrenGetter.apply(n);
            if (children != null) {
                for (Iterator<N> i = children.iterator(); i.hasNext(); ) {
                    N child = i.next();
                    if (child != null && !marked.contains(child)) {
                        marked.add(child);
                        result.add(child);
                        queue.add(child);
                    }
                }
            }
        }

        return result;
    }


}
